Online Supplement for “Coloring Graphs Using Two Colors while Avoiding Monochromatic Cycles”

Proof of the complexity of the acyclic 2-coloring problem The acyclic 2-coloring problem is defined as follows. INSTANCE: A finite directed graph G = (V,A). QUESTION: Does G have an acyclic 2-coloring? Theorem. The acyclic 2-coloring problem is NP-complete for oriented graphs. Proof: The proof is a refinement of Deb’s proof (Deb; 2008) for arbitrary directed graphs G to oriented graphs. It uses a reduction from the Not-All-Equal-3Sat problem defined as follows. INSTANCE: Set X = {x1,..., xn∗} of n ∗ variables, collection C = {C1,..., Cm∗} of m∗ clauses over X such that each clause C ` ∈ C has |C` | = 3, ` = 1,...,m∗. QUESTION: Is there a truth assignment for X such that each clause in C has at least one true literal and at least one false literal? Garey and Johnson (1979) proved that the Not-All-Equal-3Sat problem is NP-complete. The proof is structured as follows. First, we build an oriented graph G = (V,A) given the instance of the Not-All-Equal-3Sat problem. Next, we argue the equivalence of a yes